Lecture 6¶
September 18, 2024
Goal: To get comfortable using Python sets and dictionaries.
References:
- Learn Python in 7 days (Chapter 5 covers dictionaries)
- Computational Mathematics with Sage, 3.3.7-3.3.9
Mutable versus immutable objects¶
A mutable object can be changed. Immutable objects can not change. Examples:
- Numbers are immutable
- Tuples are immutable
- Lists are mutable (you can add to them, etc)
Immutable objects can be hashed: The hash of an object is a number uniquely associated to an object. This number doesn't change (over period that a program is run.)
a = 2
a = 3
hash(sqrt(2))
l = [4, 5]
l.append(7)
l
(4,5) + (7,7)
t = (4,5)
s = t
t += (7,7)
s
t
t.append(8)
Sets¶
Sets in Python/Sage store unordered collections of immutable objects.
You can define a set in several ways:
s = {3, 5, 8}
s
set('Hello')
emptyset = set()
emptyset
set?
You can convert a list or other container into a set with set().
l = [1, 2, 3, 2, -10]
s= set(l)
s
Note that sets can not contain multiple copies of the same element.
The empty set can be constructed with set():
Membership testing:
9 in s
3 in s
Adding elements:
s.add('Hi!')
s
Removing:
s.remove(2)
s
s.remove(11)
Iteration:
for x in s:
print(x)
Iteration with enumerate:
for pair in enumerate(s):
print(pair)
The number of elements in a sen is accessible with the len function:
len(s)
ZZ
ZZ.category()
ZZ.categories()
len(ZZ)
ZZ.cardinality()
for n in ZZ:
print(n)
if abs(n) > 10:
break # Drops out of the innermost loop
for n in QQ:
print(n)
if abs(n) > 3:
break # Drops out of the innermost loop
for n in ZZ:
print(n)
if abs(n) < -1:
break # Drops out of the innermost loop
Dictionaries¶
Represents a function mapping some finite collection of immutable objects to arbitrary objects. The objects in the domain are called keys. Objects in the range are called values.
Construction:
d = {'A' : 1, sqrt(2): 5, 7: [1, 2]}
d
{'A': 1, sqrt(2): 5, 7: [1, 2]}
It is also possible to construct using the dict method:
empty_dictionary = {}
empty_dictionary
{}
type(empty_dictionary)
<class 'dict'>
dict(a=4, b=7, c='Hi!')
{'a': 4, 'b': 7, 'c': 'Hi!'}
Evaluation of the function:
d
{'A': 1, sqrt(2): 5, 7: [1, 2]}
d['A']
1
d[7]
[1, 2]
d[7].append('myself')
d
{'A': 1, sqrt(2): 5, 7: [1, 2, 'myself']}
Adding a new value:
d[18] = 100
d
{'A': 1, sqrt(2): 5, 7: [1, 2, 'myself'], 18: 100}
Changing:
d[18] = 99
d
{'A': 1, sqrt(2): 5, 7: [1, 2, 'myself'], 18: 99}
Removing a key:
del d['A']
d
{sqrt(2): 5, 7: [1, 2, 'myself'], 18: 99}
The number of elements in a dictionary is accessible with len:
len(d)
3
Iteration: A for loop iterates through the keys:
for key in d:
print(key)
sqrt(2) 7 18
for key in d:
value = d[key]
print(f'{key} maps to {value}')
sqrt(2) maps to 5 7 maps to [1, 2, 'myself'] 18 maps to 99
You can also iterate through (key, value) pairs:
for pair in d.items():
print(pair)
(sqrt(2), 5) (7, [1, 2, 'myself']) (18, 99)
pair = (15, 17)
a,b = pair
a
15
b
17
It is more useful to split the pair in the for loop syntax:
for key,value in d.items():
print(f'{key} maps to {value}')
sqrt(2) maps to 5 7 maps to [1, 2, 'myself'] 18 maps to 99
Example: Sieve of Eratosthenes¶
This is a standard algorithm that computes all primes up to some integer $n$.
This follows the wikipedia article which gives the algorithm:
n = 1000
A = {}
for i in range(2, n+1):
A[i] = True
for i in srange(2, sqrt(n)+1):
if A[i]:
for j in range(i^2, n+1, i):
A[j] = False
primes = []
for i,value in A.items():
if value:
primes.append(i)
show(primes)
Example: Representing and visualizing directed graphs¶
Sage has an arrow method for drawing 2D and 3D vectors. To learn more see Sage's documentation of arrows.
arrow((0,0), (1,1), color='red', aspect_ratio=1)
We'll use two dictionaries to draw a directed graph. One with point positions, and one for edges.
points = {'A': (0,0), 'B':(1,0), 'C':(1,1), 'D':(-1/2, 1/2)}
points
{'A': (0, 0), 'B': (1, 0), 'C': (1, 1), 'D': (-1/2, 1/2)}
We can use the text function to position text in the plane and point to draw the points. You can see the documenation for text and for point.
point_list = []
for v,p in points.items():
point_list.append(p)
point_list
[(0, 0), (1, 0), (1, 1), (-1/2, 1/2)]
point(point_list, size=100, color='pink', axes=False)
text('Hi', (1, 1))
plt = point(point_list, size=150, color='pink', axes=False)
for v,p in points.items():
plt += text(v, p)
plt
Edges will be a dictionary mapping a vertex $v$ to a set of endpoints of edges leaving $v$. We start with this edge set empty, and then add some edges.
edges = dict(A = ['B'], B=['C'], C=['D'], D=['B', 'C'])
edges
{'A': ['B'], 'B': ['C'], 'C': ['D'], 'D': ['B', 'C']}
Finally we can draw the directed graph:
plt = None
for v1,p1 in points.items():
for v2 in edges[v1]:
p2 = points[v2]
if plt is None:
plt = arrow(p1, p2)
else:
plt += arrow(p1, p2)
plt
plt = point(point_list, size=150, color='pink', axes=False)
for v,p in points.items():
plt += text(v, p)
for v1,p1 in points.items():
for v2 in edges[v1]:
p2 = points[v2]
plt += arrow(p1, p2)
plt
plt = point(point_list, size=150, color='pink', axes=False,zorder=1)
for v,p in points.items():
plt += text(v, p,zorder=2)
for v1,p1 in points.items():
for v2 in edges[v1]:
p2 = points[v2]
plt += arrow(p1, p2,zorder=0)
plt
